package com.gjx.leetcode;

//105. 从前序与中序遍历序列构造二叉树
//
//根据一棵树的前序遍历与中序遍历构造二叉树。
//
//注意:
//你可以假设树中没有重复的元素。
//
//例如，给出
//
//前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7]
//返回如下的二叉树：
//
//    3
//   / \
//  9  20
//    /  \
//   15   7

public class Solution105 {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return helper(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
	}
	
	
	private TreeNode helper(int[] pre, int ps, int pe, int[] in, int is, int ie) {
		if (ps == pe) {
			return new TreeNode(pre[ps]);
		} else if (ps > pe) {
			return null;
		}
		
		TreeNode root = new TreeNode(pre[ps]);
		
		int len = 0;
		for (int i=is; i<=ie; i++) {
			if (pre[ps] == in[i]) {
				len = i-is;
				break;
			}
		}
		
		TreeNode left = helper(pre, ps+1, ps+len, in, is, is+len-1);
		TreeNode right = helper(pre, ps+len+1, pe, in, is+len+1, ie);
		
		root.left = left;
		root.right = right;
		return root;
		
	}
}
